10061. Tree Minimum element

Binary search tree is given. Return the pointer to the minimum element.

Definition of a tree:

//Java

class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int x) {

val = x;

left = null;

right = null;

}

}

// C++

class TreeNode

{

public:

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

Implement function Minimum that returns pointer to the element with minimum value in the tree.

// Java

TreeNode Minimum(TreeNode tree)

// C++

TreeNode* Minimum(TreeNode *tree)

Example

Function Minimum returns pointer to the node with value 2 – the vertex with minimum value in the tree.

SOLUTION

tree

Algorithm analysis

If tree = NULL, return NULL.

To find the vertex with the smallest value, you should start from the root and always move along the pointers to the left subtree until the left pointer of the current vertex equals NULL.

Algorithm realization

TreeNode *Minimum(TreeNode *tree)

{

If tree = NULL, return NULL.

if (tree == NULL) return tree;

Move to the left subtree until the left child of the vertex becomes NULL.

while (tree->left != NULL) tree = tree->left;

Return a pointer to the minimum element.

return tree;

}

Algorithm realization – recursion

TreeNode *Minimum(TreeNode *tree)

{

if (tree->left == NULL) return tree;

return Minimum(tree->left);

}

Java realization

TreeNode Minimum(TreeNode tree)

{

if (tree == null) return tree;

while (tree.left != null) tree = tree.left;

return tree;

}

Java realization – recursion

TreeNode Minimum(TreeNode tree)

{

if (tree.left == null) return tree;

return Minimum(tree.left);

}